#include "Heap.h"

using namespace std;
Heap::Heap(int size)
{
	_size = 0;
	_edges = new Edge[size];
}
Heap::~Heap()
{
	delete[] _edges;
}

void Heap::insert(Edge *newEdge)
{
	// insert edge at end and sift it into posistion
	_edges[_size] = *newEdge;
	sift_up(_size);
	_size++;
}

Edge* Heap::deleteMin()
{	
	// return first edge
	return &_edges[0];
}

void Heap::clear()
{
	// Delete the queue we only use it once
	_size = 0;
}

/* Losely based on the implementation at 
* http://www.algolist.net/Data_structures/Binary_heap/Insertion
*/
void Heap::sift_up(int index) 
{
	if (index != 0) 
	{			
		// parent node is always at floor(index/2)
		int parentIndex = (int) floor((float) index / 2);	
		
		if (_edges[parentIndex].cost > _edges[index].cost) 
		{
			// if cost of arent is greater then swap to maintain heap
			std::swap(_edges[parentIndex], _edges[index]);
			sift_up(parentIndex);
		}
	}
}

